堆排序(Heap Sort)

概述

堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。

什么是堆

堆的实现通过构造二叉堆,实为二叉树的一种分支。这种数据结构具有以下性质:

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
  • 堆总是一个完全二叉树,即除了最底层外,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆,而将根节点最小的堆叫做最小堆。

图源于维基百科

堆排序中如何表示堆

由于堆总是一个完全二叉树这一特性,这使得堆可以利用数组来表示,如下图所示。

对于给定的某个节点的下标i,可以很容易的计算出这个节点的父节点、左右孩子节点的下标:

  • Parent(i) = floor((i - 1) / 2),i节点的父节点下标
  • Left(i) = 2i * 1,i节点的左子节点下标
  • Right(i) = 2 * (i - 1),i节点的右子节点下标

堆排序原理(以最大堆为例)

堆排序就是把最大堆的堆顶取出,将剩余的堆继续调整为最大堆,再将堆顶的数值取出,不断重复这一过程,直至堆中只剩下一个节点为止。堆中定义以下几种操作:

  • 最大堆调整(MaxHeapify):将堆的末端子节点作调整,使得子节点永远小于父节点
  • 创建最大堆(BuildMaxHeap):将堆所有数据重新排序
  • 推排序(HeapSort):移除在第一个数据的根节点,bin并做最大堆调整的递归运算

最大堆调整(MaxHeapify)

最大堆调整的作用是保持最大堆的性质,是整个算法的核心部分。它内部的算法其实决定了堆到底是最大堆还是最小堆。

代码部分如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// array代表需要排序的数组部分
public void maxHeapAdjust(int index, int heapSize) {
int largest = index;
// 左右子节点在数组中的位置
int left = 2 * index + 1;
int right = 2 * (index + 1);

// 若左子节点大于父节点
if (left < heapSize && array[index] < array[left]) {
largest = left;
}

// 若右子节点大于父节点
if (right < heapSize && array[largest] < array[right]) {
largest = right;
}

// 倘若larget并非指向原节点index时,则证明父节点index小于某个子节点left/right
if (largest != index) {
swap(largest, index);
// 因为largest并非index,所以节点largest的堆结构也发生了变化
maxHeapAdjust(largest, heapSize);
}
}

private void swap(int i, int j) {
int tmp = queue[i];
queue[i] = queue[j];
queue[j] = tmp;
}

非递归实现版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void maxHeapAdjustWhile(int index, int heapSize) {
int largest, left, right;

while (true) {
largest = index;
left = 2 * index + 1;
right = 2 * (index + 1);

// 若左子节点大于父节点
if (left < heapSize && queue[index] < queue[left]) {
largest = left;
}

// 若右子节点大于父节点
if (right < heapSize && queue[largest] < queue[right]) {
largest = right;
}

// 倘若larget并非指向原节点index时,则证明父节点index小于某个子节点left/right
if (largest != index) {
swap(largest, index);
maxHeapAdjustWhile(largest, heapSize);
} else {
break;
}
}
}

创建最大堆(BuildMaxHeap)

创建最大堆的作用是将一个数组转换为一个最大堆。倘若堆中有n个元素,那么BuildMaxHeap就从Parent(n)开始(因为Parent(n)的节点刚刚好指向最后一个元素的父节点),从下往上地调用MaxHeapify。

代码结构如下所示:

1
2
3
4
5
6
7
public void buildMaxHeap(int heapSize) {
int parent = (heapSize - 1) / 2;
// 可以参考图思考一下,为什么这样循环递减i
for (int i = parent; i >= 0; i--) {
maxHeapAdjust(i, heapSize);
}
}

推排序(HeapSort)

堆排序是堆排序算法的接口算法部分,HeapSort先调用BuildMaxHeap将传递来的数组转换为最大堆,然后将最大堆堆顶元素与堆底最后一个元素对换,然后再重新调用MaxHeapify来保证最大堆的性质。

代码结构如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
public int[] maxHeapSort() {
int heapSize = queue.length;
buildMaxHeap(heapSize);
for (int i = heapSize - 1; i > 0; i--) {
// 交换堆顶的最大值放置数组末尾
swap(0, i);
// 重新整理最大堆,范围缩小至除已排序的节点外
maxHeapAdjust(0, i);
}

return queue;
}

时间与空间复杂度

最优时间复杂度为O(nlogn),最坏时间复杂度O(nlogn)。

总空间复杂度为O(n),辅助空间复杂度O(1)。


参考资料

堆排序

堆 (数据结构))

常见排序算法 - 堆排序 (Heap Sort)